/*
** Copyright (C) 2009 Joshua Brent Marsh <joshua@icub3d.com>
**  
** This file is part of icub3d-adt
**
** icub3d-adt is free sofware; you can redistribute it and/or modify
** it under the terms of the GNU General Public License as published by
** the Free Software Foundation; either version 3 of the License, or
** (at your option) any later version.
**  
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
** GNU General Public License for more details.
**  
** You should have received a copy of the GNU General Public License
** along with this program; if not, write to the Free Software
** Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
**  
*/

/* $Id: btree.h 36 2009-11-02 15:06:50Z joshua@icub3d.com $ */

#ifndef ICUB3D_BTREE_H
#define ICUB3D_BTREE_H 1

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <stdlib.h>

#include "function_prototypes.h"

typedef
enum btree_type
  {
    BST,
    RB
  } BtreeType;

struct btree_node
{
  int state; /* The state of the node. This could be useful for AVL, or RBs. */
  struct btree_node *parent; /* This nodes parent (useful for traversal. */
  struct btree_node *left;   /* This nodes left child. */
  struct btree_node *right;  /* This nodes right child. */
  void *data;          /* The contents of this node .*/
};

typedef
struct btree
{
  struct btree_node *root; /* The root of the tree. */
  size_t size;             /* The number of elements in the tree. */
  comp_func *comp;         /* The comparison function used on insertion. */
  BtreeType type;          /* What type of tree this is. */
} Btree;


typedef
struct btree_traverser
{
  Btree * btree;           /* The tree this traverser is using. */
  struct btree_node *cur;  /* The current node we are on. */
} BtreeTraverser;

Btree * btree_create (comp_func *, BtreeType);
void btree_destroy (Btree *, destroy_func *);

#define btree_size(b) (b)->size
void * btree_insert (Btree *, void *);
void * btree_find (Btree *, void *);
void * btree_remove (Btree *, void *);

/* Some simple traversal functions. */
void btree_traverser_init (BtreeTraverser *, Btree *);
void * btree_traverser_cur (BtreeTraverser *); 
void * btree_traverser_first (BtreeTraverser *);
void * btree_traverser_last (BtreeTraverser *);
void * btree_traverser_next (BtreeTraverser *);
void * btree_traverser_prev (BtreeTraverser *);

#endif /* ICUB3D_BTREE_H */
